This invention relates to testing of manufactured circuits, and more particularly, to testing of very large scale integrated circuits. This invention also relates to methods of generating input signal sets for testing complex digital circuits, such as VLSI chips and circuits boards containing SSI, MSI, and VLSI chips.
The advent of large scale integration has brought about enormous complexity to the testing of digital circuits. This complexity is mainly due to the reduction in the ratio of externally accessible points (primary inputs and outputs) to internal, inaccessible, points of the integrated circuit. Carefully selected sequences of input stimuli, known as test vectors, are necessary to check every internal point in the circuit so that the responses observed at the primary outputs when the circuit is faulty are distinctly different from the correct response. While test generation for purely combinational circuits (for which a number of algorithms and heuristics are known) is challenging enough due to the high circuit complexity, sequential circuit test generation poses additional complications because of the memory inherent in such circuits.
The prior art relating to integrated circuit testing can be classified into three broad categories: testing of purely combinational circuits, or of synchronous sequential circuits that were designed with particular "design for testability" techniques; testing of circuits which contain within them the hardware to perform self testing; and testing of general digital (sequential) circuits with test patterns that are externally generated and applied.
In connection with test generation techniques for combinational circuits or for sequential circuits designed for testability (e.g., containing circuitry for separating the circuit into a combinational portion and a memory), a number of methods are known which can be used for test vector generation. These include the well known D algorithm and others.
One of the more recently advanced algorithms is described, for example, in U.S. Pat. No. 4,204,633, issued May 27, 1980 to Goel. This algorithm, known as PODEM, comprises an implicit enumeration scheme for searching the n-dimensional space of primary inputs (the set of all possible input vectors, or signal sets, at the n input ports of the circuit) in order to find a test for a given fault. It has some similarities to the classic D-algorithm, but it differs from it in the sense that fast heuristics are used to truncate the searching process.
The simplest explanation of the PODEM heuristics is as follows. First, it activates a fault at a given node. The circuit is then traced backwards to identify the primary inputs that affect this node. In the process, the path or paths that are easiest to control are selected. A simple heuristic for this is the minimum distance measure from any of the primary inputs to the node in question. This insures that the decision tree search process will terminate quickest along the path in question, and an alternate path can be tried. If at any step, it is found that the current assignment of primary inputs generates a conflict, i.e., the objective cannot be accomplished, alternate choice for the primary inputs is tried until the conflict disappears, which may lead to an identified input signal set as the test for the activated fault, or indicate that the fault is untestable.
The PODEM algorithm has been studied by many researchers and even improved upon, as described, for example, by Fujiwara and Shimono in "On the Acceleration of Test Generation Algorithms," IEEE Trans. Comput. C-32, pp 1137-1144 (December 1983). Still, the test generation process is tedious and results in the testing of less than the complete set of possible faults.
Use of simulators to enhance combinational test generation algorithms has also been proposed. For example, Takamatsu and Kinoshita have proposed the use of simulators in "CONT: A Concurrent Test Generation Algorithm," Fault-Tolerant Computing Symp. (FTCS) Digest of Papers, Pittsburgh, Pa., pp. 22-27 (July 1987). In accordance with their approach the PODEM algorithm is used to generate tests for a target fault. Concurrently, all other faults are simulated, and when another fault is found close to being detected, then the target is switched to that fault. The effect of this approach is that one gets a very efficient initial fault coverage. However, because of target switching, some faults may not be tested at all. To circumvent this problem, Takamatsu and Kinoshita suggest switching to "normal" PODEM at the terminal end of the algorithm.
In the Built-In Self-Test (BIST) approaches, the circuit is designed to have a self-test mode. In this self-test mode, a part of the circuit which is specifically designed for this purpose generates test vectors and analyzes the response. The objective is to apply all possible vectors to the combinational part of the circuit. In very large circuits, either the combinational portion is partitioned into independent sections, or the whole circuit is tested by random vectors.
While scan designs (i.e., designs where the memory portion of a sequential circuit can be separated out) and self-test designs have been successfully used in many commercial systems, the extra logic added for testability has performance and cost penalties. These penalties are not always acceptable. A majority of VLSI chips manufactured today, consequently, contain neither the scan hardware nor the built-in self-test capability. Tests for these chips, as well as for many systems built with these chips, can not be generated by the algorithms described above.
Most test generators for sequential circuits have been developed on a common principle that can be summarized as follows. A combinational model of the circuit is constructed by regenerating the feedback signals from the previous-time copies of the circuit. Thus, the timing behavior of the circuit is approximated by combinational levels. Topological analysis algorithms that activate faults and sensitize paths through these multiple copies of the combinational circuit are used to generate tests. A test generator using this technique is reported by Mallela et al. in "A Sequential Circuit Test Generation System," Proc. Int. Test Conf., Philadelphia, Pa. pp. 57-61 (November 1985), and Marlett in "An Effective Test Generation System for Sequential Circuits," Proc. Des. Auto. Conf., Las Vegas, Nev., pp 250-256 (June 1986).
There are two basic problems with the above approach. First, the expansion of a sequential circuit into a combinational circuit results in increased complexity and increased memory requirements. Since each copy of the circuit represents one time frame (or vector), the complexity of tested circuits is quite limited because of the inevitable memory limitations (i.e., the number of time frames that are handled is limited). This restriction can make many testable faults "out-of-bounds" for the test generator. The second problem results from the inability of test generation algorithms to consider the timing behavior of gates. Thus, the tests can cause races and hazards in the circuit. Because of these two problems, most test generators developed on the above principles, can perform reasonably well only on circuits with up to 1,000 gates.
While most present day test generators employ the combinational model and time frame method, simulation-based methods for sequential circuits have also been reported. One method, described by Snethen in, U.S. Pat. No. 3,961,250, issued Jun. 1, 1976, constructs tests by tracing backward through the circuit in much the same way as performed in a combinational test generator, but all forward signal propagation is carried out by an event-driven simulator. This method is effective for circuits of moderate complexity (few hundred gates), but the backtracking restricts its use for very large circuits.